package DailyQuestion;

import java.util.ArrayList;
import java.util.List;

public class allPossibleFBT {
    public static void main(String[] args) {
        int n = 5;
        List<TreeNode> result = new allPossibleFBT().allPossibleFBT(n);
        System.out.println();
    }

    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> result = new ArrayList<>();
        if(n % 2 == 0)
            return result;
        if(n == 1){
            result.add(new TreeNode(0));
            return result;
        }

        for (int i = 1; i < n ; i += 2) {
            List<TreeNode> leftSubs = allPossibleFBT(i);
            List<TreeNode> rightSubs = allPossibleFBT(n - 1 -i);
            for (TreeNode leftSub : leftSubs){
                for (TreeNode rightSub : rightSubs){
                    TreeNode root = new TreeNode(0,leftSub,rightSub);
                    result.add(root);
                }
            }
        }
        return result;
    }



}
